package ali;

public class Solution_12 {

	/**
	 * 最标准的dp
	 * @param prices
	 * @return
	 */
	public int maxProfit(int[] prices) {

		if (prices == null || prices.length == 0) {
			return 0;
		}

		// 定义一个二位数组，一维表示每天的价格，二维表示状态：0 没有买入股票，1 买入股票，2 卖出股票
		int[][] dp = new int[prices.length][3];

		// 初始化第一天状态
		dp[0][0] = 0; // 第一天没有买入股票，收益为0
		dp[0][1] = -prices[0]; // 第一天买入股票的时候，还没有卖，收益为负
		dp[0][2] = 0; // 之前买入股票，现在把他卖了（这种场景第一天不存在，初始化为0）

		int maxProfit = 0; // 前一天的最大收益
		for(int i = 1; i < prices.length; i++) { // 从第二天开始遍历
			// 第i天不买没有股票的收益 = 收益等于前一天不买股票的收益
			dp[i][0] = dp[i-1][0];
			// 第i天如果要买入股票的收益 = 取最大值：1、前一天已买入股票，今天不操作。2、前一天没买入，今天买入：前一天的钱-当前股票的价格
			dp[i][1] = Math.max(dp[i-1][1], dp[i-1][0] - prices[i]);
			// 第i天如果要卖出股票的收益 = 前一天买入的股票价格 - 今天股票的价格
			dp[i][2] = dp[i-1][1] + prices[i];
			// 每一天都更新最大收益：取最大的收益
			maxProfit = getMaxProfit(maxProfit, dp[i][0], dp[i][1], dp[i][2]);
		}
		return maxProfit;
	}

	public int getMaxProfit(int... profits) {
		int maxProfit = profits[0];
		for (int i = 1; i < profits.length; i++) {
			if (profits[i] > maxProfit) {
				maxProfit = profits[i];
			}
		}
		return maxProfit;
	}

}